package LeetCode.interview;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;

import util.LogUtils;

/*
 * 
 原题

	 Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
	
	 For example: Given the below binary tree and sum = 22,
	
	 5
	 / \
	 4   8
	 /   / \
	 11  13  4
	 /  \      \
	 7    2      1
	 return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
 题目大意
	
	 给定一个二叉树和一个值sum，判断是否存在一个从根节点到叶子节点的路径，使得路径上每个节点值之和等于sum?

 解题思路
		 大体思路就是遍历从根到叶子的每一条路径，并求和。只要相等，就返回true，否则一直遍历下去，最后返回false。
		 从根节点一路遍历下去。遍历每一条路径
		 因为：sum值是从根节点到叶子节点的所有节点值之和
		 所以：每遇到一个节点就将sum-当前节点的值,
		 最后遇到叶子节点时, 判断最后sum剩下的值是否等于叶子节点的值
		 如果是,则找到


 * @Date 2017-09-14 09：20
 */
public class _112_Path_Sum {

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}

		public TreeNode(int x, TreeNode l, TreeNode r) {
			val = x;
			left = l;
			right = r;
		}
	}

	public boolean hasPathSum(TreeNode node, int sum) {
		if (node == null)
			return false; // 路径遍历结束,未找到
		else if (node.left == null && node.right == null)
			return sum == node.val; // 遇到叶子结点(路径最后一个节点),看是否和剩余的sum值一致
		else
			return (hasPathSum(node.left, sum - node.val) || hasPathSum(
					node.right, sum - node.val)); // 每遇到一个节点就用sum减去当前节点的值
	}

	private TreeNode newTree2() {
		return new TreeNode(1, new TreeNode(2, new TreeNode(4, new TreeNode(6),
				new TreeNode(7, null, new TreeNode(8))), new TreeNode(5)),
				new TreeNode(3, null, null));
	}

	private TreeNode newTree1() {
		return new TreeNode(1, null, null);
	}

	// 中序遍历：看下结果
	public void traverse(TreeNode rs) {
		if (rs == null)
			return;
		traverse(rs.left);
		LogUtils.print(rs.val);
		traverse(rs.right);
	}

	public static void main(String[] args) {
		_112_Path_Sum obj = new _112_Path_Sum();
		LogUtils.println("结果", obj.hasPathSum(obj.newTree2(), 22));
	}
}
